Studia [A]
Limit pamięci: 64 MB
Studia na Uniwersytecie Bajtockim (UB) składają się z etapów, które
odpowiadają polskim semestrom studiów, tyle że może ich być mniej lub więcej.
Każdy student w trakcie nauki na uniwersytecie składa wiele podań do dziekana
swojego wydziału, które wpływają na jego przebieg studiów.
W szczególności dzięki podaniom studenci mogą zmieniać etapy
studiów, na których się aktualnie znajdują.
Złożenie podania może mieć także konsekwencje finansowe dla studenta -
zarówno korzystne (uzyskanie stypendium), jak i niekorzystne
(opłaty za zaliczanie dodatkowych przedmiotów, powtarzanie przedmiotów itd.).
Bajtazar jest leniwym, ale wyjątkowo sprytnym studentem UB.
Przez lata zbierał dane o różnych podaniach, jakie składali inni studenci,
i dla każdego z nich zapamiętywał, jak wpłynęło ono na aktualny etap studiów
składającego go studenta oraz jakie były jego konsekwencje finansowe.
Bajtazarowi nie zależy bynajmniej na szybkim zakończeniu studiów, lecz na
osiągnięciu jak najwyższych korzyści materialnych.
Gwarancję nieograniczonych korzyści daje sytuacja, w której można
rozpocząć studia na jakimś etapie, następnie złożyć kolejno pewną liczbę
podań tak, aby na sam koniec wrócić na wyjściowy etap studiów i w wyniku
całego procesu zarobić dodatnią liczbę bajtalarów.
Bajtazar jest bardzo cierpliwy w dążeniu do celu: może sobie pozwolić
na złożenie wielu podań, ba, nawet na złożenie tego samego podania
wielokrotnie w trakcie całego procesu, o ile tylko wszystko zakończy się
upragnionym zyskiem.
W swoich planach zakłada on, że dziekan pracuje w sposób deterministyczny, to
znaczy że wynik złożenia ustalonego podania z archiwum Bajtazara jest
zawsze taki sam.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opisy wszystkich podań, jakie
Bajtazar zdołał dotychczas zebrać,
- wyznaczy wszystkie takie numery etapów studiów na UB, które
dają gwarancję nieograniczonych korzyści finansowych,
- wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite oraz
(, ), oddzielone pojedynczym
odstępem i oznaczające liczbę etapów studiów na UB oraz liczbę podań
znajdujących się w archiwum Bajtazara.
Kolejne wierszy zawiera po trzy liczby całkowite , oraz
(, , ), pooddzielane
pojedynczymi odstępami i oznaczające: etap studiów, na którym to podanie
zostało złożone przez studenta, etap studiów, na którym znalazł się on
w wyniku złożenia podania oraz konsekwencje finansowe, jakie student
poniósł (wartość dodatnia oznacza zysk studenta, a ujemna - stratę).
Żadna para nie pojawi się na wejściu więcej niż raz, ale
pojawić się mogą równocześnie pary i .
Wyjście
Pierwszy wiersz wyjścia powinien zawierać jedną liczbę ,
oznaczającą liczbę różnych etapów studiów, z których rozpocząwszy studia,
Bajtazar może osiągnąć nieograniczone korzyści finansowe.
Drugi wiersz powinien zawierać liczb całkowitych ze zbioru
, pooddzielanych pojedynczymi odstępami i oznaczających
wszystkie takie etapy.
Numery etapów powinny być wymienione w kolejności rosnącej.
Przykład
Dla danych wejściowych:
8 8
1 2 3
1 3 -3
5 4 4
6 5 -1
6 7 -1
7 8 5
8 6 2
4 8 -3
poprawną odpowiedzią jest:
5
4 5 6 7 8
Autor zadania: Jakub Radoszewski.